import UIKit

/*
 189. 旋转数组
 中文：https://leetcode-cn.com/problems/rotate-array/
 英文：https://leetcode.com/problems/rotate-array/
*/
class Rotate {
    //解法1
    //时间复杂度：O(n*k)O(n∗k)
    //空间复杂度：O(1)O(1)
    func rotate(_ nums: inout [Int], _ k: Int) {
        for _ in 0..<k {
            var previous = nums[nums.count-1]
            for j in 0..<nums.count {
                let temp = nums[j]
                nums[j] = previous
                previous = temp
            }
        }
    }

    //解法2 空间换时间
    //时间复杂度： O(n)O(n) 。将数字放到新的数组中需要一遍遍历，另一边来把新数组的元素拷贝回原数组。
    //空间复杂度： O(n)O(n)。另一个数组需要原数组长度的空间。
    func rotate1(_ nums: inout [Int], _ k: Int) {
        var a:[Int] = Array(repeating: 0, count: nums.count)
        for i in 0..<nums.count {
            a[(i+k)%nums.count] = nums[i]
        }
        for i in 0..<nums.count {
            nums[i] = a[i]
        }
    }

    //解法3反转
    func rotate3(_ nums: inout [Int], _ k: Int) {
        let k = k % nums.count
        reverse(&nums, 0, nums.count-1)
        reverse(&nums, 0, k-1)
        reverse(&nums, k, nums.count-1)
    }
    func reverse(_ nums: inout [Int], _ start: Int, _ end: Int) {
        var start = start, end = end
        while start < end {
            let temp = nums[start]
            nums[start] = nums[end]
            nums[end] = temp
            start += 1
            end -= 1
        }
    }
}

var nums1 = [0,1,2,3,4]
let rotate = Rotate()
//rotate.rotate(&nums1, 2)
//rotate.rotate1(&nums1, 2)
rotate.rotate3(&nums1, 2)
nums1
